#include<iostream>
#include<vector>
#include<fstream>
#include<algorithm>
#include<set>
#include<queue>
#include<list>
#include<stack>
using namespace std;

struct TreeNode
{
    char value;
    list<TreeNode*> listChildren;
    
    TreeNode(void)
    : value(0)
    {
    }
};

class Tree
{
	friend class Graph;
public:
    Tree(void)
    :root(NULL)
    {
    }
    ~Tree(void)
    {
        FreeNode(root);
    }
    void Output(void)
    {
        stack<TreeNode*> stkNode;
        stack<int> stkIndex;
        TreeNode* pNode = root;
        
        char strTemp[100] = {0};
        char* pStr = strTemp;
        *pStr++ = '(';
        
        while (NULL != pNode || !stkNode.empty())
        {
            if (NULL != pNode)
            {
                *pStr++ = pNode->value;
                *pStr++ = '(';
                
                stkNode.push(pNode);
                stkIndex.push(0);
                
                if (!pNode->listChildren.empty())
                {
                    pNode = pNode->listChildren.front();
                }
                else
                {
                    pNode = NULL;
                }
            }
            else
            {
                stkNode.pop();
                if (stkNode.empty())
                {
                    pStr--;
                    *pStr++ = ')';
                    *pStr = ')';
                    
                    break;
                }
                
                pNode = stkNode.top();
                stkIndex.pop();
                stkIndex.top()++;
                
                pStr--;
                if (',' == *pStr)
                {
                    *pStr++ = ')';
                }
                *pStr++ = ',';
                
                list<TreeNode*>::iterator it = pNode->listChildren.begin();
                advance(it, stkIndex.top());
                if (it != pNode->listChildren.end())
                {
                    pNode = *it;
                }
                else
                {
                    pNode = NULL;
                }
            }
        }
        
        cout<< strTemp <<endl;
    }
private:
    TreeNode* root;
    void FreeNode(TreeNode* pNode)
    {
        if (NULL != pNode)
        {
            list<TreeNode*>::iterator it, itEnd = pNode->listChildren.end();
            for (it = pNode->listChildren.begin(); it != itEnd; ++it)
            {
                FreeNode(*it);
            }
            
            delete pNode;
            pNode = NULL;
        }
    }
};

typedef char GNode;

struct ArcCell
{
    GNode startNode;
    GNode endNode;
    
    ArcCell(void)
    : startNode(0)
    , endNode(0)
    {
    }
    
    friend istream& operator>>(istream& is, ArcCell& arc)
    {
        is>> arc.startNode >> arc.endNode;
        
        return is;
    }
};

struct ArcNode
{
    GNode node;
    vector<ArcCell> m_vecArc;
    
    ArcNode(void)
    : node(0)
    {
    }
};

class Graph
{
public:
    void BuildGraph(char const* file)
    {
        ifstream ifs(file);
        
        ArcCell arc;
        while (ifs>> arc)
        {
            AddNodeByArc(arc);
            swap(arc.startNode, arc.endNode);
            AddNodeByArc(arc);
        }
        
        ifs.close();
    }
	void DFSForest(void)
	{
		set<GNode> setNode;

		vector<ArcNode>::iterator it, itEnd = m_vecNode.end();
		for (it = m_vecNode.begin(); it != itEnd; ++it)
		{
			GNode node = it->node;
			if (setNode.end() == setNode.find(node))
			{
				TreeNode* pNode = new TreeNode;
				pNode->value = node;

				DFSTree(pNode, node, setNode);

				Tree tree;
				tree.root = pNode;
				tree.Output();
			}
		}
	}
private:
    vector<ArcNode> m_vecNode;
    void AddNodeByArc(const ArcCell& arc)
    {
        vector<ArcNode>::iterator it = FindNode(arc.startNode);
        if (it == m_vecNode.end())
        {
            ArcNode arcNode;
            arcNode.node = arc.startNode;
            arcNode.m_vecArc.push_back(arc);
            
            m_vecNode.push_back(arcNode);
        }
        else
        {
            it->m_vecArc.push_back(arc);
        }
    }
    vector<ArcNode>::iterator FindNode(const GNode& node)
    {
        vector<ArcNode>::iterator it, itEnd = m_vecNode.end();
        for (it = m_vecNode.begin(); it != itEnd; ++it)
        {
            if (it->node == node)
            {
                break;
            }
        }
        
        return it;
    }
	void DFSTree(TreeNode* pNode, GNode node, set<GNode>& setNode)
	{
		setNode.insert(node);

		vector<ArcNode>::iterator itNode = FindNode(node);
		if (itNode != m_vecNode.end())
		{
			vector<ArcCell>::iterator itArc, itArcEnd = itNode->m_vecArc.end();
			for (itArc = itNode->m_vecArc.begin(); itArc != itArcEnd; ++itArc)
			{
				node = itArc->endNode;
				if (setNode.end() == setNode.find(node))
				{
					TreeNode* pTreeNode = new TreeNode;
					pTreeNode->value = node;

					DFSTree(pTreeNode, node, setNode);
					pNode->listChildren.push_back(pTreeNode);
				}
			}
		}
	}
};

int main(void)
{
	Graph gTest;
	gTest.BuildGraph("graph.txt");

	cout<< "=============Generate Tree.=============\n";
	gTest.DFSForest();
    
    system("pause");
}
